第1章绪论

#密码学

习题1

1. 简述分组密码的设计原则，比较其与序列密码、哈希函数的不同

（1）

分组密码的设计主要基于香农所提出的混淆和扩散两大准则，目的是使得明文与密文之间的统计规律被打乱，攻击者难以从统计的角度来攻击。

其中扩散指的就是使得密文中某一个比特同时包含明文中多个比特的信息，换句话说就是明文和密文之间不是一对一的代换关系，而是复杂的由多到一的函数关系，这样就相当于将对应明文的统计特性散布到了密文中。

混淆应该不用多说，它的目的是增强密文的“随机性”，仍然是使得攻击者难以找到规律。

其实还有另一条原则也不能漏掉：Kerckhoff 原则 （译作柯克霍夫，读作“肯霍夫”？）
也就是密码系统的全部算法上的细节都得公开，只有明文和密钥（在非对称加密里是私钥）是不公开的，不然的话该密码系统的安全性就得不到保障了。

（2）

序列密码更普遍的称呼是流密码，它的加密是逐比特的，而分组密码是分组加密的。

哈希函数应该不算是加密算法，因为它基本没法解密，也没有用到密钥。

2. 分组密码的安全性评估方法有哪些？分别需要具备哪些条件？调研各种分析方法的发展现状

对于分组密码的安全性评估主要分为两种：抵抗现有分析方法 和 可证明安全性。

对于第一种，目前常用的分析方法主要就是 差分分析 和 线性分析。这两种还可以进行很多变化，进化成更多的方法，比如：截断差分分析、不可能差分分析、积分分析、差分-线性分析等等。关于这些方法的详细介绍，我之后估计会在另一本书的笔记里写一写。

从另一种角度来考虑的话，可以把几乎所有密码攻击分成下面4类：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击。其攻击强度依次递增。

对于第二种，这本书没有怎么介绍，而且我也不了解，所以暂且不谈。

关于发展现状，分组秘密的安全性评估方法在朝着 自动化 和 轻量化 的方向发展，比如说 自动化分析工具，使用混合整数线性规划（MILP）等数学方法来搜索差分或线性特征。（这大概是大热门吧，因为我所了解的一个研究小组就在弄和这相关的东西）

其实我觉得还得加上密码标准 国产化 这一方面（国密算法的大力推广），毕竟不能被卡脖子了。

3. 设有分组长度为3比特的代换密码 2,5,3,7,6,4,0,1

题目写得很简略，它的意思是：设加密函数 $y = f (x)$ 将 x 代换成 y

x	0	1	2	3	4	5	6	7
y	2	5	3	7	6	4	0	1
x	000	001	010	011	100	101	110	111
y	010	101	011	111	110	100	000	001

（1）计算输入差分为2，输出差分分别为 0,1,2,3,4,5,6,7 的概率

分别计算就行了，有点像概率论里的题（
$f (0) \oplus f (0 \oplus 2) = 1$
$f (1) \oplus f (1 \oplus 2) = 2$
$f (2) \oplus f (2 \oplus 2) = 1$
$f (3) \oplus f (3 \oplus 2) = 2$
$f (4) \oplus f (4 \oplus 2) = 6$
$f (5) \oplus f (5 \oplus 2) = 5$
$f (6) \oplus f (6 \oplus 2) = 6$
$f (7) \oplus f (7 \oplus 2) = 5$

x	0	1	2	3	4	5	6	7
P	$0$	$\frac{1}{4}$	$\frac{1}{4}$	$0$	$0$	$\frac{1}{4}$	$\frac{1}{4}$	$0$

（2）计算输入掩码为3，输出掩码分别为 0,1,2,3,4,5,6,7 的概率

$0 \oplus 3 = f (0) \oplus 1$
$1 \oplus 3 = f (1) \oplus 7$
$2 \oplus 3 = f (2) \oplus 2$
$3 \oplus 3 = f (3) \oplus 7$
$4 \oplus 3 = f (4) \oplus 1$
$5 \oplus 3 = f (5) \oplus 2$
$6 \oplus 3 = f (6) \oplus 5$
$7 \oplus 3 = f (7) \oplus 5$

x	0	1	2	3	4	5	6	7
P	$0$	$\frac{1}{4}$	$\frac{1}{4}$	$0$	$0$	$\frac{1}{4}$	$0$	$\frac{1}{4}$

（3）写出此密码体制的3个布尔函数表达式

布尔函数表达式
看到这个要求时我还有点摸不着头脑：什么叫密码体制的布尔函数表达式？难道这个代换密码是可以用布尔函数的形式来表达的吗？这样不就从非线性的变成线性的了吗？
查了一下之后才知道，布尔函数是可以非线性的（也就是可以有乘法），那么这一问应该是要把每一位的表达式写出来。

此代换密码可写为： $f : {0, 1}^{3} \to {0, 1}^{3}$
（将一个三维的向量空间映射到另一个三维的向量空间）

至于怎么写表达式，我觉得这只能靠穷举了……
（实质上是解一个0-1变量的方程组）
（感觉这个问题可以引申到逻辑电路那个领域，不过我目前还不怎么了解）
正常构造密码应该是先写出表达式再给出对应的代换表，但这个题反过来了，其实相当于是在对这个密码体制实施攻击。

用AI得到的结果如下（因为我懒得自己去算了）：
输入比特记为 $b_{2}, b_{1}, b_{0} (b_{0} 为最低有效位 L S B ， b_{2} 为最高有效位 M S B)$
输出比特记为 $c_{2}, c_{1}, c_{0} (c_{0} 为 L S B ， c_{2} 为 M S B)$
表达式如下：
$c_{2} = f_{2} = b_{0} \oplus b_{2} \oplus b_{0} b_{2} \oplus b_{1} b_{2}$
$c_{1} = f_{1} = 1 \oplus b_{0} \oplus b_{0} b_{1} \oplus b_{1} b_{2}$
$c_{0} = f_{3} = b_{0} \oplus b_{1} \oplus b_{0} b_{1} \oplus b_{0} b_{2} \oplus b_{1} b_{2}$

验证了一下，这几个表达式的确是正确的

def f2(b2,b1,b0):
	return b0^b2^(b0*b2)^(b1*b2)
def f1(b2,b1,b0):
	return 1^b0^(b0*b1)^(b1*b2)
def f0(b2,b1,b0):
	return b0^b1^(b0*b1)^(b0*b2)^(b1*b2)

for i in [0,1]:
    for j in [0,1]:
        for k in [0,1]:
            print(f'{i}{j}{k}  {f1(i,j,k)}{f2(i,j,k)}{f3(i,j,k)}')

更新：
多学了一点知识后，我才知道这个问题是可以不用穷举的……
详见布尔函数的表示与转换